inf = 99999

''''
Floyd-Warshall算法 DP O(n^3)
'''


def floyd(D):
    n = len(D)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if D[i][j] > D[i][k] + D[k][j]:
                    D[i][j] = D[i][k] + D[k][j]


D = [
    [0, 2, 6, 4],
    [inf, 0, 3, inf],
    [7, inf, 0, 1],
    [5, inf, 12, 0]
]

floyd(D)
print(D)
